package twice.class02;

import com.sun.xml.internal.ws.util.exception.LocatableWebServiceException;

//区间和
//leetcode：327
public class CountRangeSum {
    public static int countRangeSum(int[] nums, int lower, int upper){
        if(nums == null || nums.length < 2){return 0;}
        int[] preSum = new int[nums.length];
        preSum[0] = nums[0];
        for(int i = 1;i < nums.length;i++){
            preSum[i] = preSum[i-1] + nums[i];
        }
        return process(preSum,0,nums.length-1,lower,upper);
    }
    static int process(int[] preSum,int L,int R,int lower, int upper){
        if(L==R){
            if(preSum[L] <= upper && preSum[L] >= lower){
                return 1;
            }else{return 0;}
        }
        int M = L + (R - L)/2;
        return process(preSum,L,M,lower,upper)+process(preSum,M+1,R,lower,upper)+merege(preSum,L,M,R,lower,upper);
    }
    static int merege(int[] preSum,int L,int M,int R,int l,int u){
            int ans = 0;
            int windowL = L;
            int windowR = L;
            for(int i = M + 1;i <= R;i++) {
                int max = preSum[i] - l;
                int min = preSum[i] - u;
                while (windowL <= M && preSum[windowL] < min) {
                    windowL++;
                }
                while (windowR <= M && preSum[windowR] <= max) {
                    windowR++;
                }
                ans += Math.max(0,windowR-windowL);
            }

        int[] help = new int[R - L + 1];

        int p1 = L;
        int p2 = M + 1;
        int i = 0;
        while(p1 <= M && p2 <= R){

            help[i++] = preSum[p1] < preSum[p2] ? preSum[p1++] : preSum[p2++];
        }
        while (p1 <= M) {
            help[i++] = preSum[p1++];
        }
        while (p2 <= R) {
            help[i++] = preSum[p2++];
        }
        for (i = 0; i < help.length; i++) {
            preSum[L + i] = help[i];
        }
        return ans;
    }
    }
